package leetcode.editor.template.sort;

/**
 * 快速排序（递归法）
 */
public class quickSortTest {
    public static void main(String[] args) {
        // 调用
        int[] nums = {4, 1, 3, 2, 5};
        quickSortTest quickSortTest = new quickSortTest();
        quickSortTest.quickSort(nums, 0, nums.length - 1);
        // quickSortTest.quickSortByTailCall(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    /**
     * 递归进行快排
     *
     * @param nums
     * @param l
     * @param r
     */
    public void quickSort(int[] nums, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分操作
        int i = partitionByRandom(nums, l, r);
        // 递归左（右）子数组执行哨兵划分
        quickSort(nums, l, i - 1);
        quickSort(nums, i + 1, r);
    }

    /**
     * Tail Call 优化过的递归快排
     *
     * @param nums
     * @param l
     * @param r
     */
    public void quickSortByTailCall(int[] nums, int l, int r) {
        // 子数组长度为 1 时终止递归
        while (l < r) {
            // 哨兵划分
            int i = partition(nums, l, r);
            // 仅递归至较短子数组，控制递归深度
            if (i - 1 < r - i) {
                quickSortByTailCall(nums, l, i - 1);
                l = i + 1;
            } else {
                quickSortByTailCall(nums, i + 1, r - 1);
                r = i - 1;
            }
        }
    }

    /**
     * 一次快排的操作
     *
     * @param nums
     * @param l
     * @param r
     * @return
     */
    int partition(int[] nums, int l, int r) {
        int i = l, j = r;
        // 以nums[l]作为哨兵
        while (i < j) {
            // 先找到j，交换之后会出现把大的交换过来了，例如[2,1,3]
            while (i < j && nums[j] >= nums[l]) j--; // 找到右边第一个小于哨兵的数
            while (i < j && nums[i] <= nums[l]) i++; // 找到左边第一个大于哨兵的数
            swap(nums, i, j);   // 交换找到2个元素
        }
        swap(nums, l, i); // 交换哨兵
        return i;   // 分割的下标
    }

    /**
     * 一次快排的操作(随机基准数优化)
     *
     * @param nums
     * @param l
     * @param r
     * @return
     */
    int partitionByRandom(int[] nums, int l, int r) {
        // 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
        int random = (int)(l + Math.random() * (r - l + 1));
        swap(nums, l, random);
        int i = l, j = r;
        // 以nums[l]作为哨兵
        while (i < j) {
            while (i < j && nums[j] > nums[l]) j--; // 找到右边第一个小于哨兵的数
            while (i < j && nums[i] < nums[l]) i++; // 找到左边第一个大于哨兵的数
            swap(nums, i, j);   // 交换找到2个元素
        }
        swap(nums, l, i); // 交换哨兵
        return i;   // 分割的下标
    }

    public void swap(int[] nums, int i, int j) {
        // 交换 nums[i] 和 nums[j]
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}